package com.algorithm.hqy;


/**
 * @Classname SingleLinkedList
 * @Date 2019/9/17 13:53
 * @auther by hqy
 * 单链表，链表是以节点的形式存储的，每个节点都有data域，和next域
 */
public class SingleLinkedList<T> {

    private Node head = new Node<T>() {

        @Override
        public int compareTo(T comparator) {
            return -1;
        }
    };


    /**
     * @param []
     * @return void
     * @Description 链表反转，非常巧妙的方法
     */
    public void reverseList() {
        Node temp = head.next;
        /**
         *help是辅助变量
         */
        Node help = new Node() {
            @Override
            public int compareTo(Object comparator) {
                return -1;
            }
        };

        /**
         *在遍历链表时候，temp中取出的每一个节点都放在help的next后面
         */
        while (temp != null) {

            Node next = temp.next;

            temp.next = help.next;

            help.next = temp;
            temp = next;
        }
        head.next = help.next;


    }

    public void addUnsorted(Node node) {
        Node temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
        }
        temp.next = node;
    }

    public void addSorted(Node node) {
        Node temp = head;
        while (true) {
            if (temp.next == null) {
                temp.next = node;
                break;
            }
            if (temp.next.compareTo(node) > 0) {
                node.next = temp.next;
                temp.next = node;
                break;
            }
            temp = temp.next;
        }

    }

    public boolean existsNode(Node node) {
        Node temp = head;
        while (true) {
            if (temp.next == null) {
                return false;
            }
            if (temp.next.compareTo(node) == 0) {
                return true;
            }
            temp = temp.next;
        }
    }

    public int deleteNode(Node node) {
        Node temp = head;
        while (true) {
            if (temp.next == null) {
                return 0;
            }
            if (temp.next.compareTo(node) == 0) {
                temp.next = temp.next.next;
                return 1;
            }
            temp = temp.next;
        }

    }

    public void show() {
        Node temp = head.next;

        while (true) {
            if (temp.next == null) {
                System.out.println("没有啦~~~~~");
                break;
            } else {
                System.out.println(temp);
            }

            temp = temp.next;
        }
    }


}

abstract class Node<T> {
    public Node next;

    public abstract int compareTo(T comparator);

}
